---
id: 587d8256367417b2b2512c79
title: 接続行列
challengeType: 1
forumTopicId: 301644
dashedName: incidence-matrix
---

# --description--

グラフを表すもう一つの方法は、 <dfn>接続行列</dfn>に入れることです。

<dfn>接続行列</dfn> は二次元 (2D) 配列です。 一般に接続行列は、2 つの次元の間で 2 種類のクラスのオブジェクトを関連付けます。 このような行列は隣接行列に似ています。 しかし、行と列の意味がそれとは異なります。

グラフにはエッジとノードがあります。 この 2 つは、私たちが使う「オブジェクトの 2 種類のクラス」です。 この行列では、行がノード、列がエッジを表します。 したがって、行と列の数が違っていても構いません。

各列は一意のエッジを表します。 また、各エッジは 2 つのノードを接続します。 2 つのノードの間に 1 本のエッジがあることを示すために、特定の列の 2 行に 1 を入れます。 下に示したのは、ノード 1 とノード 3 の間に 1 本のエッジがある、3 ノードのグラフです。

<blockquote>    1<br>   ---<br>1 | 1<br>2 | 0<br>3 | 1</blockquote>

4 本のエッジと 4 つのノードを持つ接続行列の例はこちらです。 列はエッジ、行はノード自体であることを思い出してください。

<blockquote>    1 2 3 4<br>   --------<br>1 | 0 1 1 1<br>2 | 1 1 0 0<br>3 | 1 0 0 1<br>4 | 0 0 1 0</blockquote>

次のコードは、同じことを JavaScript で実装したものです。

```js
var incMat = [
  [0, 1, 1, 1],
  [1, 1, 0, 0],
  [1, 0, 0, 1],
  [0, 0, 1, 0]
];
```

有向グラフを作成するには、特定のノードを離れるエッジに `-1` を使用し、ノードに入るエッジに `1` を使用します。

```js
var incMatDirected = [
  [ 0, -1,  1, -1],
  [-1,  1,  0,  0],
  [ 1,  0,  0,  1],
  [ 0,  0, -1,  0]
];
```

グラフのエッジに <dfn>重み</dfn> を付けることもできます。 これまでに見てきたエッジは、単にエッジの有無が二項 (`0` または `1`) で表された、<dfn>重み付けされていない</dfn>エッジです。 用途によって重みを変えることができます。 異なる重みは 1 より大きい数字として表されます。

# --instructions--

5 つのノードと 4 本のエッジを持つ、無向グラフの接続行列を作成してください。 この行列は多次元配列でなければなりません。

これら 5 つのノードは次のような関係にあります。 1 本目のエッジは 1 番目と 2 番目のノードの間にあります。 2 本目のエッジは 2 番目と 3 番目のノードの間にあります。 3 本目のエッジは 3 番目と 5 番目のノードの間にあります。 4 本目のエッジは 4 番目と 2 番目のノードの間にあります。 すべてのエッジの重みは 1 であり、エッジの順序には意味があります。

# --hints--

`incMatUndirected` には 5 つのノードのみが含まれている必要があります。

```js
assert(
  incMatUndirected.length === 5 &&
    incMatUndirected
      .map(function (x) {
        return x.length === 4;
      })
      .reduce(function (a, b) {
        return a && b;
      })
);
```

1 番目と 2 番目のノードの間には 1 本目のエッジが必要です。

```js
assert(incMatUndirected[0][0] === 1 && incMatUndirected[1][0] === 1);
```

2 番目と 3 番目のノードの間には、2 本目のエッジが必要です。

```js
assert(incMatUndirected[1][1] === 1 && incMatUndirected[2][1] === 1);
```

3 番目と 5 番目のノードの間には、3 本目のエッジが必要です。

```js
assert(incMatUndirected[2][2] === 1 && incMatUndirected[4][2] === 1);
```

2 番目と 4 番目のノードの間には、4 本目のエッジが必要です。

```js
assert(incMatUndirected[1][3] === 1 && incMatUndirected[3][3] === 1);
```

# --seed--

## --seed-contents--

```js
var incMatUndirected = [

];
```

# --solutions--

```js
var incMatUndirected = [[1, 0, 0, 0],[1, 1, 0, 1],[0, 1, 1, 0],[0, 0, 0, 1],[0, 0, 1, 0]];
```
